/*  slfdivml.cpp  by K.Tsuru  */
// function ID = 211    DRADIX, BRADIX
/*************************************************************************
SLong and SInteger classes
It provides a sub-function for the multiplication between multi-precision
integers.
*************************************************************************/
#ifndef SN_H
#include "sn.h"
#endif

/*
Let q=n.figure.size(), U = R^q
m=M[d-1]*U^(d-1)+....M[1]*U+M[0].
m*n=(M[d-1]*n)*U^(d-1)+....(M[1]*n)*U+M[0]*n.
*/
SLong DivLLMult(const SLong& m, const SLong& n){
    uint mh = m.aHead+1, nh = n.aHead+1;
    uint mf = ceilpow2(mh), nf = ceilpow2(nh), div = mf/nf;
#ifndef NDEBUG
assert(div > 1);
#endif
    if(nh < m.FFTMinSize()) return NLLMult(m, n);

    SLong result, p;
    SLong* w = new SLong[div];
    uint j, pos;
    for(j = 0, pos = 0; j < div; j++, pos += nf){
        result.SLCutOut(w[j], m, pos, nf);
    }
    result = w[0]*n;
    for(j = 1; j < div; j++){
        p = n*w[j];
        p.ShiftArray(int(j*nf));
        result = LLAdd(result, p);  // result += p;
    }
    delete[] w;
    result.SetSign(m.Sign()*n.Sign());
    return result;
}